//
//  myEncode.c
//  imageCompression
//
//  Created by cocoa on 16/5/6.
//  Copyright © 2016年 cocoa. All rights reserved.
//

#include "myEncode.h"

#define BITS 9

typedef unsigned char byte;


static void outputCode(unsigned int crntCode, int *outbyte, int *outbits, int crntBits, byte *outBuff, int *outsz);


int encodeBuf(const unsigned char *buf, int size_in, unsigned char *outBuf, int *size_out) {
    int max = 0;
    int table[1 << BITS];
    int tableCount = 0;
    
    int outsz = 0;
    int outbyte = 0;
    int outbits = 0;
    
    byte sign[256] = {0};
    for (int i = 0; i < size_in; ++i) {
        if (sign[buf[i]] == 0) {
            max ++ ;
            sign[buf[i]] = 1;
        }
    }
    max -- ;
    int bits = 0;
    while (max > 0) {
        bits ++ ;
        max >>= 1;
    }
    if (bits < 2) {
        bits = 2;
    }
    printf("%i\n", bits);
    
    max = 1 << bits;
    int CLEAR_CODE = max;
    int EOF_CODE = max + 1;
    int crntBits = bits + 1;
    
    unsigned int crntCode = buf[0];
    for (int i = 1; i < size_in; ++i) {
        int v = buf[i];
        int k = (crntCode << 8) + v;
        int code = -1;
        for (int i = 0; i < tableCount; ++i) {
            if (table[i] == k) {
                code = i;
                break;
            }
        }
        if (code >= 0) {
            crntCode = code + EOF_CODE + 1;
            continue;
        }
        outputCode(crntCode, &outbyte, &outbits, crntBits, outBuf, &outsz);
//        printf("table==%i, %i\n", tableCount, k >> 8);
        
        if (tableCount + EOF_CODE >= (1 << crntBits) - 1 && crntBits < BITS) {
            crntBits ++ ;
        }
        if (tableCount + EOF_CODE >= (1 << BITS) - 1) {
            outputCode(CLEAR_CODE, &outbyte, &outbits, crntBits, outBuf, &outsz);
            crntBits = bits + 1;
            tableCount = 0;
        } else {
            table[tableCount ++ ] = k;
        }
        crntCode = v;
    }
    outputCode(crntCode, &outbyte, &outbits, crntBits, outBuf, &outsz);
    outputCode(EOF_CODE, &outbyte, &outbits, crntBits, outBuf, &outsz);
    if (outbits > 0) {
        outBuf[outsz ++ ] = outbyte & 0xff;
    }
    *size_out = outsz;
    return 0;
}

static void outputCode(unsigned int crntCode, int *outbyte, int *outbits, int crntBits, byte *outBuf, int *outsz) {
    *outbyte |= crntCode << *outbits;
    *outbits += crntBits;
    while (*outbits >= 8) {
        outBuf[(*outsz) ++ ] = *outbyte & 0xff;
        *outbyte >>= 8;
        *outbits -= 8;
    }
}

